IEEE INFOCOM 2021

Session F-7

Caching 2

Conference

10:00 AM — 11:30 AM EDT

Local

May 13 Thu, 7:00 AM — 8:30 AM PDT

Attack Resilience of Cache Replacement Policies

Tian Xie (Pennsylvania State University, USA); Ting He (Penn State University, USA); Patrick McDaniel and Namitha Nambiar (Pennsylvania State University, USA)

3

Caches are pervasively used in computer networks to speed up access by reusing previous communications, where various replacement policies are used to manage the cached contents. The replacement policy of a cache plays a key role in its performance, and is thus extensively engineered to achieve a high hit ratio in benign environments. However, some studies showed that a policy with a higher hit ratio in benign environments may be more vulnerable to denial of service (DoS) attacks that intentionally send requests for unpopular contents. To understand the cache performance under such attacks, we analyze a suite of representative replacement policies under the framework of TTL approximation in how well they preserve the hit ratios for legitimate users, while incorporating the delay for the cache to obtain a missing content. We further develop a scheme to adapt the cache replacement policy based on the perceived level of attack. Our analysis and validation on real traces show that although no single policy is resilient to all the attack strategies, suitably adapting the replacement policy can notably improve the attack resilience of the cache.

Rate Allocation and Content Placement in Cache Networks

Khashayar Kamran, Armin Moharrer, Stratis Ioannidis and Edmund Yeh (Northeastern University, USA)

3

We introduce the problem of optimal congestion control in cache networks, whereby both rate allocations and content placements are optimized jointly. We formulate this as a maximization problem with non-convex constraints, and propose solving this problem via (a) a Lagrangian barrier algorithm and (b) a convex relaxation. We prove different optimality guarantees for each of these two algorithms; our proofs exploit the fact that the non-convex constraints of our problem involve DR-submodular functions.

Joint Cache Size Scaling and Replacement Adaptation for Small Content Providers

Jiahui Ye, Zichun Li, Zhi Wang and Zhuobin Zheng (Tsinghua University, China); Han Hu (Beijing Institute of Technology, China); Wenwu Zhu (Tsinghua University, China)

2

Elastic Content Delivery Networks (Elastic CDNs) have been introduced to support explosive Internet traffic growth by providing small Content Providers (CPs) with just-in-time services. Due to the diverse requirements of small CPs, they need customized adaptive caching modules to help them adjust the cached contents to maximize their long-term utility. The traditional adaptive caching module is usually a built-in service in a cloud CDN. They adaptively change cache contents using size-scaling-only methods or strategy-adaptation-only methods. A natural question is: can we jointly optimize size and strategy to achieve tradeoff and better performance for small CPs when renting services from elastic CDNs? The problem is challenging because the two decision variables could involve both discrete and categorical variables, where discrete variables have an intrinsic order while categorical variables do not. In this paper, we propose a distribution-guided reinforcement learning framework JEANA to learn the joint cache size scaling and strategy adaptation policy. We design a distribution-guided regularizer to keep the intrinsic order of discrete variables. More importantly, we prove that our algorithm has a theoretical guarantee of performance improvement. Trace-driven experimental results demonstrate our method can improve the hit ratio while reducing the rental cost.

Self-adjusting Advertisement of Cache Indicators with Bandwidth Constraints

Itamar Cohen (Politecnico di Torino, Italy); Gil Einziger (Ben-Gurion University Of The Negev, Israel); Gabriel Scalosub (Ben-Gurion University of the Negev, Israel)

0

Cache advertisements reduce the access cost by allowing users to skip the cache when it does not contain their datum. Such advertisements are used in multiple networked domains such as 5G networks, wide area networks, and information-centric networking. The selection of an advertisement strategy exposes a trade-off between the access cost and bandwidth consumption. Still, existing works mostly apply a trial-and-error approach for selecting the best strategy, as the rigorous foundations required for optimizing such decisions is lacking.

Our work shows that the desired advertisement policy depends on numerous parameters such as the cache policy, the workload, the cache size, and the available bandwidth. In particular, we show that there is no ideal single configuration. Therefore, we design an adaptive, self-adjusting algorithm that periodically selects an advertisement policy. Our algorithm does not require any prior information about the cache policy, cache size, or workload, and does not require any apriori configuration. Through extensive simulations, using several state-of-the-art cache policies, and real workloads, we show that our approach attains a similar cost to that of the best static configuration (which is only identified in retrospect) in each case.

Session Chair

Sergey Gorinsky (IMDEA Networks Institute, Spain)

Session F-8

LoRa

Conference

12:00 PM — 1:30 PM EDT

Local

May 13 Thu, 9:00 AM — 10:30 AM PDT

Modeling Communication Reliability in LoRa Networks with Device-level Accuracy

Verónica Toro-Betancur and Gopika Premsankar (Aalto University, Finland); Mariusz Slabicki (Institute of Theoretical and Applied Informatics, Polish Academy of Sciences, Poland); Mario Di Francesco (Aalto University, Finland)

3

Long Range (LoRa) is a low-power wireless communication technology for long-range connectivity, extensively used in the Internet of Things. Several works in the literature have analytically characterized the performance of LoRa networks, with particular focus on scalability and reliability. However, most of the related models are limited, as they cannot account for factors that occur in practice, or make strong assumptions on how devices are deployed in the network. This article proposes an analytical model that describes the delivery ratio in a LoRa network with device-level granularity. Specifically, it considers the impact of several key factors that affect real deployments, including multiple gateways and channel variation. Therefore, the proposed model can effectively evaluate the delivery ratio in realistic network topologies, without any restrictions on device deployment or configuration. It also accurately characterizes the delivery ratio of each device in a network, as demonstrated by extensive simulations in a wide variety of conditions, including diverse networks in terms of node deployment and link-level parameter settings. The proposed model provides a level of detail that is not available in the state of the art, and it matches the simulation results within an error of a few percentage points.

Jamming of LoRa PHY and Countermeasure

Ningning Hou, Xianjin Xia and Yuanqing Zheng (The Hong Kong Polytechnic University, Hong Kong)

1

LoRaWAN forms a one-hop star topology where LoRa nodes send data via one-hop up-link transmission to a LoRa gateway. If the LoRa gateway can be jammed by attackers, the LoRa gateway may not be able to receive any data from any nodes in the network. Our empirical study shows that although LoRa physical layer (PHY) is robust and resilient by design, it is still vulnerable to synchronized jamming chirps. Potential protection solutions (e.g., collision recovery, parallel decoding) may fail to extract LoRa packets if an attacker transmits synchronized jamming chirps at high power. To protect the LoRa PHY from such attacks, we propose a new protection method that can separate LoRa chirps from jamming chirps by leveraging their difference in the received signal strength in power domain. We note that the new protection solution is orthogonal to existing solutions which leverage the chirp misalignment in time domain or the frequency disparity in frequency domain. We conduct experiments with COTS LoRa nodes and software defined radios. The results show that synchronized jamming chirps at high power can jam all previous solutions, while our protection solution can effectively protect LoRa gateways from the jamming attacks.

Radio Frequency Fingerprint Identification for LoRa Using Spectrogram and CNN

Guanxiong Shen, Junqing Zhang and Alan Marshall (University of Liverpool, United Kingdom (Great Britain)); Linning Peng (Southeast University, China); Xianbin Wang (Western University, Canada)

0

Radio frequency fingerprint identification (RFFI) is an emerging device authentication technique that relies on intrinsic hardware characteristics of wireless devices. We designed an RFFI scheme for Long Range (LoRa) systems based on spectrogram and convolutional neural network (CNN). Specifically, we used spectrogram to represent the fine-grained time-frequency characteristics of LoRa signals. In addition, we revealed that the instantaneous carrier frequency offset (CFO) is drifting, which will result in misclassification and significantly compromise the system stability; we demonstrated CFO compensation is an effective mitigation. Finally, we designed a hybrid classifier that can adjust CNN outputs with the estimated CFO. The mean value of CFO remains relatively stable, hence it can be used to rule out CNN predictions whose estimated CFO falls out of the range. We performed experiments in real wireless environments using 20 LoRa devices under test (DUTs) and a Universal Software Radio Peripheral (USRP) N210 receiver. By comparing with the IQ-based and FFT-based RFFI schemes, our spectrogram-based scheme can reach the best classification accuracy, i.e., 97.61% for 20 LoRa DUTs.

Pyramid: Real-Time LoRa Collision Decoding with Peak Tracking

Zhenqiang Xu, Pengjin Xie and Jiliang Wang (Tsinghua University, China)

1

LoRa, as a representative Lower Power Wide Area Network (LPWAN) technology, shows great potential in providing low power and long range wireless communication. Real LoRa deployments, however, suffer from severe collisions. Existing collision decoding methods cannot work well for low SNR LoRa signals. Most LoRa collision decoding methods process collisions offline and cannot support real-time collision decoding in practice. To address these problems, we propose Pyramid, a real-time LoRa collision decoding approach. To the best of our knowledge, this is the first real-time multi-packet LoRa collision decoding approach in low SNR. Pyramid exploits the subtle packet offset to separate packets in a collision. The core of Pyramid is to combine signals in multiple windows and transfers variation of chirp length in multiple windows to robust features in the frequency domain that are resistant to noise. We address practical challenges including accurate peak recovery and feature extraction in low SNR signals of collided packets. We theoretically prove that Pyramid incurs a very small SNR loss (< 0.56 dB) to original LoRa transmissions. We implement Pyramid using USRP N210 and evaluate its performance in a 20-nodes network. Evaluation results show that Pyramid achieves real-time collision decoding and improves the throughput by 2.11×.

Session Chair

Janise McNair (University of Florida)

Session F-9

Performance

Conference

2:30 PM — 4:00 PM EDT

Local

May 13 Thu, 11:30 AM — 1:00 PM PDT

On the Performance of Pipelined HotStuff

Jianyu Niu and Fangyu Gai (The University of British Columbia, Canada); Mohammad Jalalzai (The University of British Columbia); Chen Feng (University of British Columbia, Canada)

0

HotStuff is a state-of-the-art Byzantine fault-tolerant consensus protocol. It can be pipelined to build large-scale blockchains. One of its variants called LibraBFT is adopted in Facebook's Libra blockchain. Although it is well known that pipelined HotStuff is secure against up to 1/3 of Byzantine nodes, its performance in terms of throughput and delay is still under-explored. In this paper, we develop a multi-metric evaluation framework to quantitatively analyze pipelined HotStuff's performance with respect to its chain growth rate, chain quality, and latency. We then propose several attack strategies and evaluate their effects on the performance of pipelined HotStuff. Our analysis shows that the chain growth rate (resp, chain quality) of pipelined HotStuff under our attacks can drop to as low as 4/9 (resp, 12/17) of that without attacks when 1/3 nodes are Byzantine. As another application, we use our framework to evaluate certain engineering optimizations adopted by LibraBFT. We find that these optimizations make the system more vulnerable to our attacks than the original pipelined HotStuff. Finally, we provide two countermeasures to thwart these attacks. We hope that our studies can shed light on the rigorous understanding of the state-of-the-art pipelined HotStuff protocol as well as its variants.

Practical Analysis of Replication-Based Systems

Florin Ciucu (University of Warwick, United Kingdom (Great Britain)); Felix Poloczek (University of Warwick / TU Berlin, Germany); Lydia Y. Chen (IBM Zurich Research Laboratory, Switzerland); Martin Chan (University of Warwick, Germany)

0

Task replication has been advocated as a practical solution to reduce response times in parallel systems. The analysis of replication-based systems typically rests on some strong assumptions: Poisson arrivals, exponential service times, or independent service times of the replicas. This study is motivated not only by several studies which indicate that these assumptions are unrealistic, but also by some elementary observations highlighting some contriving behaviour. For instance, when service times are not exponential, adding a replication factor can stabilize an unstable system, i.e., having infinite delays, but a tempting higher replication factor can push the system back in a perilous unstable state. This behaviour disappears however if the replicas are sufficiently correlated, in which case any replication factor would even be detrimental. Motivated by the need to dispense with such common yet unrealistic and misleading assumptions, we provide a robust theoretical framework to compute stochastic bounds on response time distributions in general replication systems subject to Markovian arrivals, quite general service times, and correlated replicas. Numerical results show that our bounds are accurate and improve state-of-the-art bounds in the case of Markovian arrivals by as much as three orders of magnitude. We apply our results to a practical application and highlight that correctly setting the replication factor crucially depends on both the service time distributions of the replicas and the degree of correlation amongst.

WebMythBusters: An In-depth Study of Mobile Web Experience

Seonghoon Park and Yonghun Choi (Yonsei University, Korea (South)); Hojung Cha (Yonsei University, S. Korea, Korea (South))

0

The quality of experience (QoE) is an important issue for users when accessing the web. Although many metrics have been designed to estimate the QoE in the desktop environment, few studies have confirmed whether the QoE metrics are valid in the mobile environment. In this paper, we ask questions regarding the validity of using desktop-based QoE metrics for the mobile web and find answers. We first classify the existing QoE metrics into several groups according to three criteria and then identify the differences between the mobile and desktop environments. Based on the analysis, we ask three research questions and develop a system, called WebMythBusters, for collecting and analyzing mobile web experiences. Through an extensive analysis of the collected user data, we find that (1) the metrics focusing on fast completion or fast initiation of the page loading process cannot estimate the actual QoE, (2) the conventional scheme of calculating visual progress is not appropriate, and (3) focusing only on the above-the-fold area is not sufficient in the mobile environment. The findings indicate that QoE metrics designed for the desktop environment are not necessarily adequate for the mobile environment, and appropriate metrics should be devised to reflect the mobile web experience.

SOBA: Session optimal MDP-based network friendly recommendations

Theodoros Giannakas (EURECOM, France); Anastasios Giovanidis (Sorbonne Université & CNRS-LIP6, France); Thrasyvoulos Spyropoulos (EURECOM, France)

2

Caching content over CDNs or at the network edge has been solidified as a means to improve network cost and offer better streaming experience to users. Furthermore, nudging the users towards low-cost content has recently gained momentum as a strategy to boost network performance. We focus on the problem of optimal policy design for Network Friendly Recommendations (NFR). We depart from recent modeling attempts, and propose a Markov Decision Process (MDP) formulation. MDPs offer a unified framework that can model a user with random session length. As it turns out, many state-of-the-art approaches can be cast as subcases of our MDP formulation. Moreover, the approach offers flexibility to model users who are reactive to the quality of the received recommendations. In terms of performance, for users consuming an arbitrary number of contents in sequence, we show theoretically and using extensive validation over real traces that the MDP approach outperforms myopic algorithms both in session cost as well as in offered recommendation quality. Finally, even compared to optimal state-of-art algorithms targeting specific subcases, our MDP framework is significantly more efficient, speeding the execution time by a factor of 10, and enjoying better scaling with the content catalog and recommendation batch sizes.

Session Chair

Marie-Jose Montpetit (Concordia University, Canada)

Session F-10

Protocols

Conference

4:30 PM — 6:00 PM EDT

Local

May 13 Thu, 1:30 PM — 3:00 PM PDT

802.11ad in Smartphones: Energy Efficiency, Spatial Reuse, and Impact on Applications

Shivang Aggarwal (Northeastern University, USA); Moinak Ghoshal (Northeastern University, Boston, MA, USA); Piyali Banerjee (University at Buffalo, USA); Dimitrios Koutsonikolas (Northeastern University, USA); Joerg Widmer (IMDEA Networks Institute, Spain)

1

We present an extensive experimental evaluation of the performance and power consumption of the 60 GHz IEEE 802.11ad technology on commercial smartphones. We also compare 802.11ad against its main competitors in the 5 GHz band - 802.11ac and, for first time, 802.11ax, on mobile devices. Our performance comparison focuses on two aspects that have not been extensively studied before: (i) dense multi-client and multi-AP topologies and (ii) popular mobile applications under realistic mobility patterns. Our power consumption study covers both non-communicating and communicating modes. We also present the first study of the power saving mode in 802.11ad-enabled smartphones and its impact on performance. Our results show that 802.11ad is better able to address the needs of emerging bandwidth-intensive applications in smartphones than its 5 GHz counterparts. At the same time, we identify several key research directions towards realizing its full potential.

Age-Dependent Distributed MAC for Ultra-Dense Wireless Networks

Dheeraj Narasimha (Arizona State University, USA); Srinivas G Shakkottai (Texas A&M University, USA); Lei Ying (University of Michigan, USA)

0

We consider an ultra-dense wireless network with N channels and M = N devices. Messages with fresh information are generated at each device according to a random process and need to be transmitted to an access point. The value of a message decreases as it ages, so each device searches for an idle channel to transmit the message as soon as it can. However, each channel probing is associated with a fixed cost (energy), so a device needs to adapt its probing rate based on the "age" of the message. At each device, the design of the optimal probing strategy can be formulated as an infinite horizon Markov Decision Process (MDP) where the devices compete with each other to find idle channels. While it is natural to view the system as a Bayesian game, it is often intractable to analyze such a system. Thus, we use the Mean Field Game (MFG) approach to analyze the system in a large-system regime, where the number of devices is very large, to understand the structure of the problem and to find efficient probing strategies. We present an analysis based on the MFG perspective. We begin by characterizing the space of valid policies and use this to show the existence of a Mean Field Nash Equilibrium (MFNE) in a constrained set for any general increasing cost functions with diminishing rewards. Further we provide an algorithm for computing the equilibrium for any given device, and the corresponding age-dependent channel probing policy.

Delay-Tolerant Constrained OCO with Application to Network Resource Allocation

Juncheng Wang and Ben Liang (University of Toronto, Canada); Min Dong (Ontario Tech University, Canada); Gary Boudreau and Hatem Abou-zeid (Ericsson, Canada)

0

We consider online convex optimization (OCO) with multi-slot feedback delay, where an agent makes a sequence of online decisions to minimize the accumulation of time-varying convex loss functions, subject to short-term and long-term constraints that are possibly time-varying. The current convex loss function and the long-term constraint function are revealed to the agent only after the decision is made, and they may be delayed for multiple time slots. Existing work on OCO under this general setting has focused on the static regret, which measures the gap of losses between the online decision sequence and an offline benchmark that is fixed over time. In this work, we consider both the static regret and the more practically meaningful dynamic regret, where the benchmark is a time-varying sequence of per-slot optimizers. We propose an efficient algorithm, termed Delay-Tolerant Constrained-OCO (DTC-OCO), which uses a novel constraint penalty with double regularization to tackle the asynchrony between information feedback and decision updates. We derive upper bounds on its dynamic regret, static regret, and constraint violation, proving them to be sublinear under mild conditions. We further apply DTC-OCO to a general network resource allocation problem, which arises in many systems such as data networks and cloud computing. Simulation results demonstrate substantial performance gain of DTC-OCO over the known best alternative.

Multicast Communications with Varying Bandwidth Constraints

Yuval Emek and Shay Kutten (Technion, Israel); Mordechai Shalom (Tel-Hai College & Technion, Israel); Shmuel Zaks (Technion, Israel)

0

To find a maximum number of communication requests that can be satisfied concurrently, is a fundamental network scheduling problem. In this work we investigate the problem of finding a maximum number of multicast requests that can be scheduled simultaneously in a tree network in which the edges and links have heterogeneous bandwidth limitations. This problem generalizes two problems studied in the literature: maximum k-colorable subgraph in chordal graphs, maximum multi-commodity flow in trees. The problem is NP-hard and admits a 1.585-approximation in the special case of homogeneous bandwidth limitations. We first show that the problem is harder to approximate when the bandwidth limitations are heterogeneous, i.e. vary from link to link and from node to node. We then generalize of a classical algorithm and obtain an M-approximation where M is the maximum number of leaves of the communication subtrees. Surprisingly, variants of the same algorithm, are used in the literature at least four times to solve related problems. There exists a polynomial-time algorithm for the special case of unicast requests and star topology. We generalize this result and relax the second requirement so that the set of unicast requests share a common vertex with no restriction on the tree topology.

Session Chair

Jiangchuan Liu (Simon Fraser University, Canada)

Program at a Glance